\documentclass[oneside]{homework} %%Change `twoside' to `oneside' if you are printing only on the one side of each sheet.

\studname{Ran Yu}
\studmail{ry2239@columbia.edu}
\coursename{Analysis of Algorithm}
\hwNo{3}
\uni{ry2239}

\usepackage{graphicx}
\usepackage{subfigure}
\begin{document}
\maketitle

\section*{Problem 1}
\section*{Problem 2}
a) To solve this problem, we use 2 steps, first, we sort the integers by the number of digits, and second, we use radix sort to sort the integers which have same length. And for that we can get the integers with more digits are bigger, so that we can then arrange all the sorted digits by the number of digits.\\
Let us assume there is $m$ integers. The first step we take $O(m)$ running time to group integers with same length. And the second step, for each group that integers with same length, the radix sort take $O(k_i)$, and $k_i$ is the number of integers that the digit number is i. So the all running time for step 2 is $O(\sum (k_i)\times i)$, that is $O(n)$, the total number of all the integers.\\
So that the all running time would be $O(n+m)=O(n)$\\
b) The string sorting problem is a little more complicated. We can use $trie-tree$ to solve it, but as we learn about sorting this chapter, we choose to use modified counting sort to solve it.\\
For that if the first letter is alphabetically larger, the string is larger, we sort the strings on first letter by counting sort. We make an modified counting sort algorithm as below:\\
 1. Empty string would be put first;\\
 2. Sort the strings on first letter and group them by their first letter;\\
 3. Repeat step2 within each group, with strings in the group that first letter removed;\\
No we consider about running time, for every string, it is sorted by $i+1$ time when its length is i. So the running time would be $O(n+m)$, $m$ is the number of strings, for that $m<n$, running time is $O(n)$.
\section*{Problem 3}
$DELET-HEAP(A,i)\\
~~~exchange~A[i]\leftrightarrow A[heap-size[A]]\\
~~~heap-size[A]=heap-size[A]-1\\
~~~MAX-HEAPIFY(A,1)$
\section*{Problem 4}
a)
\begin{figure}[!ht] 
     \centering   
     \includegraphics[width=9cm, height=6cm]{p4.jpg} 
     \caption{BST} 
\end{figure}
\\
Let's take the way of searching the key $8$; hence, the set $A,~B,~C$ are:\\
$B={5,~9,~8}$\\
$A={3,~2,~4,~7}$\\
$C={12}$\\
We pick $5$ from set $A$, and pick $7$ from set $B$, we can see that $5<7$.\\
b)
\section*{Problem 5}
a) First prove that an AVL tree of height h has at least Fh nodes, where Fh is the hth Fibonacci number.\\
h=1, the AVL tree has at least 1 node;\\
h=2, the AVL tree has at least 2 node;\\
h=3, the AVL tree has at least 4 node, 1+2+1=4;\\
$\dots$\\
We can see that the number of nodes that an AVL tree at least have, would be $N_h=1+N_{h-1}+N_{h-2}$. This conclusion is obvious, for that an AVL tree that has least nodes, could be consisted of AVL trees with least nodes that height is $h-1$ and height is $h-2$, with an root node.\\
In this way, we can get that $N_h=F_{h+2}-1$, for $F_{h+2}=\frac{\Phi^{h+2}}{\sqrt{5}}$, $h=O(\log n)$\\
b)For the procedure $BALANCE(x)$, we have to handle 4 different conditions.\\
step 1: Find the lowest node $ln$ of the tree that rooted at $x$;\\
\begin{figure}[!h]
     \centering  
     \subfigure[RR]{ \includegraphics[width=3.5cm, height=2.8cm]{rr.jpg}}
     \subfigure[LL]{ \includegraphics[width=3.5cm, height=2.8cm]{ll.jpg}}
     \subfigure[RL]{ \includegraphics[width=3.5cm, height=2.8cm]{rl.jpg}}
     \subfigure[LR]{ \includegraphics[width=3.5cm, height=2.8cm]{lr.jpg}}
 \end{figure}\\
step 2: \\
~~~~~~if $ln$ in the left child of left child of x: $Right-Rotate(x.left)$\\
~~~~~~if $ln$ in the right child of right child of x: $Left-Rotate(x.right)$\\
~~~~~~if $ln$ in the left child of right child of x: $Right-Rotate(x.right); Left-Rotate(x)$\\
~~~~~~if $ln$ in the right child of left child of x: $Left-Rotate(x.left); Right-Rotate(x)$\\
c)For the procedure $AVL-Insert(x, z)$,\\
Step 1: Insert z into subtree of $x$ at the right position.($TREE-Insert(x,z)$)\\
Step 2: Find the lowest unbalanced node $k$ of subtree of $x$, call the function $BALANCE(k)$;
Step 3: If $x$ is still not balance, repeat step 2 until $x$ is balanced.
d) For the function of $AVL-Insert(x,z)$, the first step of insertion costs $O(\log n)$ running time, and every rotation cost a constant time. 



\end{document}